1. Field of the Invention
The present invention relates to a technique for calculating matrices through computer processing, and more particularly to a funny matrix multiplication (FMM) calculation.
2. Description of Related Art
The term “FMM” means a matrix calculation process in which “add” (addition) and “multiply” (multiplication) in a normal matrix multiplication process are replaced by a min operation and an add operation. In other words, the definition of FMM is to calculate an equation, C[i, j]=mink{A[i, k]+B[k, j]}, with respect to all (i, j) for two input matrices A and B. Although FMM is not limited to a square matrix, each of the matrices A and B is assumed to be a square matrix of n×n in this specification as a matter of convenience.
FMM is applicable to a shortest path calculation, image processing, or the like. For example, a document, “A. V. Aho, J. E. Hopcroft, and J. D. Ullman, ‘The Design and Analysis of Computer Algorithms,’ Addison-Wesley, 1974,” describes an example of a technique for a shortest path calculation using FMM.
In FMM, the value from an addition “va[k]+vb[k]” is calculated in the order of k=1 to n with respect to two vectors va and vb each having a length n to find the minimum value as a basic calculation. Specifically, calculating an addition “mink{va[k]+vb[k]}” is the main processing and the processing is performed n2 times, and therefore the entire FMM processing takes O(n3) time.
In recent years, demand for further speeding up the shortest path calculation is increasing in the fields of traffic simulation, car navigation, and the like. Therefore, an algorithm for speeding up FMM is described in the following document.
A document, “J. J. McAuley and T. S. Gaetano, ‘An expected-case sub-cubic solution to the all-pairs shortest path problem in R,’ arXiv: 0912.0975v1, 2009,” discloses calculating permutations a1, a2, . . . , an and b1, b2, . . . , bn satisfying va[a1]≦va[a2]≦ . . . ≦va[an] and vb[b1]≦vb[b2]≦ . . . ≦vb[bn] before calculating mink{va[k]+vb[k]} with respect to two vectors va and vb. In the entire FMM processing, the pre-calculation is achieved only by performing sort processing 2n times in total, and therefore the calculation takes only O(n2 log n) time in total.